package leetcode_1_200;

public class LeeCode_99_failed {
    public static void main(String[] args) {
//        recoverTree(new TreeNode(3, new TreeNode(1), new TreeNode(4, new TreeNode(2), null)));
//        recoverTree(new TreeNode(1, new TreeNode(3, null, new TreeNode(2)), null));
//          recoverTree(new TreeNode(2, null, new TreeNode(1)));
          recoverTree(new TreeNode(2, new TreeNode(3), new TreeNode(1)));
    }

    private static void recoverTree(TreeNode root) {
        long[] m = new long[2];
        boolean[] flag = new boolean[1];
        helper(root, Long.MIN_VALUE, Long.MAX_VALUE, m, flag);
        if (!flag[0]) {
            helper2(root, m);
        }
        System.out.println();
    }

    private static void helper(TreeNode node, long min, long max, long[] m, boolean[] flag) {
        if (node.left != null) {
            if (node.left.val <= min) {
                if (node.right != null && (node.right.val < Math.max(min, node.val) || node.right.val >= max)){
                    int tmp = node.right.val;
                    node.right.val = node.left.val;
                    node.left.val = tmp;
                    flag[0] = true;
                    return;
                }
                m[0] = min;
                m[1] = node.left.val;
                node.left.val = (int) m[0];
                return;
            } else if (node.left.val >= Math.min(max, node.val)) {
                if (node.right != null && (node.right.val < Math.max(min, node.val) || node.right.val >= max)){
                    int tmp = node.right.val;
                    node.right.val = node.left.val;
                    node.left.val = tmp;
                    flag[0] = true;
                    return;
                }
                m[0] = Math.min(max, node.val);
                m[1] = node.left.val;
                node.left.val = (int) m[0];
                return;
            } else
                helper(node.left, min, Math.min(max, node.val), m, flag);
        }
        if (node.right != null) {
            if (node.right.val < Math.max(min, node.val)) {
                m[0] = Math.max(min, node.val);
                m[1] = node.right.val;
                node.right.val = (int) m[0];
            } else if (node.right.val >= max) {
                m[0] = max;
                m[1] = node.right.val;
                node.right.val = (int) m[0];
            } else
                helper(node.right, Math.max(min, node.val), max, m, flag);
        }
    }

    private static void helper2(TreeNode node, long[] m){
        if (node == null)
            return;
        if (node.val == m[0]){
            node.val = (int) m[1];
        }else {
            helper2(node.left, m);
            helper2(node.right, m);
        }
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
